package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/22 11:56
 */
public class Title1514II {

    class State{
        int id;

        /**
         * start - > id (prob)
         */
        double prob;

        public State(int id, double prob) {
            this.id = id;
            this.prob = prob;
        }
    }

    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        //<i,<j, value>>
        Map<Integer, Map<Integer, Double>> graph = new HashMap<>();
        for (int i = 0; i < edges.length; i++) {
            graph.computeIfAbsent(edges[i][0], g -> new HashMap<>()).put(edges[i][1], succProb[i]);
            graph.computeIfAbsent(edges[i][1], g -> new HashMap<>()).put(edges[i][0], succProb[i]);
        }
        double[] dist = new double[n];
        dist[start] = 1.0;
        Queue<State> queue = new PriorityQueue<>((a, b) -> (Double.compare(b.prob, a.prob)));
        queue.offer(new State(start, 1));
        while (!queue.isEmpty()) {
            State state = queue.poll();
            int curId = state.id;
            double curProb = state.prob;
            if (curId == end) {
                return dist[end];
            }
            if (curProb < dist[curId]) {
                continue;
            }
            Map<Integer, Double> orDefault = graph.getOrDefault(curId, new HashMap<>());
            Set<Integer> integers = orDefault.keySet();
            for (int nextId : integers) {
                double nextPro = curProb * orDefault.get(nextId);
                if (nextPro > dist[nextId]) {
                    dist[nextId] = nextPro;
                    queue.offer(new State(nextId, nextPro));
                }
            }
        }
        return 0;
    }

    public static void main(String[] args) {

    }
}
